English+GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>15-Puzzle</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">15-Puzzle</span></h1>

</header>

</div>

<p>Das <b>15-Puzzle</b>, auch <b>Fünfzehnerspiel</b>, <b>14-15-Puzzle</b>, <b>Schiebepuzzle</b>, <b>Schieberätsel</b>, <b>Schiebefix,</b> <b>Schiebefax</b> oder <b>Ohne-Fleiß-kein-Preis-Spiel</b> genannt, ist ein <a href="Geduldsspiel" title="Geduldsspiel">Geduldsspiel</a>. Es wurde zwischen 1870 und 1880 in den <a href="Vereinigte_Staaten" title="Vereinigte Staaten">Vereinigten Staaten</a> vom Postangestellten Noyes Palmer Chapman erfunden. Das Spiel besteht aus 15 Kacheln, von 1 bis 15 durchnummeriert, die auf den 16 Feldern eines Vier-mal-vier-<a href="Quadrat" title="Quadrat">Quadrats</a> angebracht sind. Ein Feld (das „Loch“) bleibt also frei. Eine (vertikal oder horizontal) benachbarte Kachel kann jeweils in das freie Feld hineingeschoben werden. Die Aufgabe besteht nun darin, durch Verschieben der Kacheln die Zahlen von 1 bis 15 aufsteigend anzuordnen.

</p><p>Je nach Ausgangsstellung gibt es verschiedene Varianten des Spiels, insbesondere das 14-15-Puzzle, bei dem in der Ausgangsstellung lediglich die Zahlen 14 und 15 vertauscht sind, wodurch das Puzzle unlösbar wird. Heutige Ausgaben des Spiels werden meist in der gewünschten Anordnung ausgeliefert; Der Spieler verschiebt („mischt“) die Kacheln zunächst und versucht dann, das Puzzle wieder in die geordnete Ausgangsstellung zu bringen. Bei dieser Spielvariante ist mithin garantiert, dass die Aufgabe lösbar ist.

</p>

<div class="mw-heading mw-heading2"><h2 id="Geschichte">Geschichte</h2></div>

<p>Das Spiel wurde von dem Postangestellten Noyes Palmer Chapman erfunden, der seinen Freunden im Jahr 1874 ein ähnliches Puzzle zeigte. Bei diesem ging es darum, 16 nummerierte Blöcke in die Form eines <a href="Magisches_Quadrat" title="Magisches Quadrat">magischen Quadrates</a> zu bringen. Die ersten Kopien des 15-Puzzles gelangten nach <a href="Syracuse_(New_York)" title="Syracuse (New York)">Syracuse</a> im Staat <a href="New_York_(Bundesstaat)" title="New York (Bundesstaat)">New York</a> zu Frank Chapman, dem Sohn von Noyes. Von dort verbreitete sich das Spiel weiter nach Watch Hill und schließlich nach <a href="Hartford_(Connecticut)" title="Hartford (Connecticut)">Hartford</a> in <a href="Connecticut" title="Connecticut">Connecticut</a>, wo Schüler der amerikanischen Schule für Hörbehinderte das Puzzle in großen Auflagen fertigten und im Dezember 1879 als Weihnachtsgeschenke in <a href="Boston" title="Boston">Boston</a>, <a href="Massachusetts" title="Massachusetts">Massachusetts</a> verkauften. Matthias Rice, der Besitzer eines Geschäftes für ausgefallene Holzgegenstände, entdeckte eines dieser Puzzles und fing an, diese umgehend selbst herzustellen und als „Gem Puzzle“ auf den Markt zu bringen.

</p><p>Die 15 Spielsteine bzw. Kacheln lagen dabei lose in einer kleinen Box und die Spielanleitung lautete: »Place the blocks in the box irregularly, then move until in regular order« (zu Deutsch etwa: „Setze die Spielsteine in beliebiger Anordnung in die Box, dann verschiebe sie, bis sie sich in Reihenfolge befinden“).<sup id="cite_ref-Gem_Puzzle_1-0" class="reference"><a href="#cite_note-Gem_Puzzle-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>Gegen Ende Januar 1880 setzte der Zahnarzt Charles Pevey ein Preisgeld für die Lösung des 15-Puzzles aus. Der erste <a href="Trend_(Soziologie)" title="Trend (Soziologie)">Trend</a> für das Spiel war in den USA im Februar, in <a href="Kanada" title="Kanada">Kanada</a> im März und in <a href="Europa" title="Europa">Europa</a> im April 1880 zu sehen. Der Trend war bereits im Juli desselben Jahres aber wieder im Rückgang. Erst neun Jahre später wurde das Spiel in <a href="Japan" title="Japan">Japan</a> eingeführt.<sup id="cite_ref-slocum-sonneveld_2-0" class="reference"><a href="#cite_note-slocum-sonneveld-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>Chapman wollte das 15-Puzzle am 21. Februar 1880 als „Block Solitaire Puzzle“ zum Patent anmelden, stieß beim Patentamt aber auf Ablehnung, da sich sein Spiel nicht ausreichend von dem am 20. August 1878 erteilten Patent für das von Ernest U. Kinsey entwickelte Spiel „Puzzle-Blocks“ zu unterscheiden schien.<sup id="cite_ref-slocum-sonneveld_2-1" class="reference"><a href="#cite_note-slocum-sonneveld-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>Der Rätselspezialist <a href="Samuel_Loyd" title="Samuel Loyd">Samuel Loyd</a> behauptete von 1891 bis zu seinem Tod im Jahr 1911, dass er der Erfinder dieses Rätsels sei, konnte dies aber niemals belegen. Neueren Untersuchungen zufolge wurde er sogar als Lügner entlarvt.<sup id="cite_ref-slocum-sonneveld_2-2" class="reference"><a href="#cite_note-slocum-sonneveld-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-cut-the-knot_3-0" class="reference"><a href="#cite_note-cut-the-knot-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Während des <a href="Erster_Weltkrieg" title="Erster Weltkrieg">Ersten Weltkriegs</a> wurde das 15-er Puzzle als „Geduldspiel für den Schützengraben“ produziert.

</p>

<div class="mw-heading mw-heading2"><h2 id="Aufgabenstellungen">Aufgabenstellungen</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Ursprüngliches_Puzzle"><span id="Urspr.C3.BCngliches_Puzzle"></span>Ursprüngliches Puzzle</h3></div>

<p>Beim „Gem Puzzle“, das Matthias Rice 1879 produzierte und verkaufte,<sup id="cite_ref-Gem_Puzzle_1-1" class="reference"><a href="#cite_note-Gem_Puzzle-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> nahm der Spieler zu Beginn die Steine heraus und setzte sie beliebig in die Box. Anschließend bestand die Aufgabe darin, durch Verschieben der Steine die Zahlen zeilenweise aufsteigend anzuordnen. Dabei ergeben sich folgende mathematische Zusammenhänge:

</p>

<ul><li>Es gibt 16! = 20922789888000 ≈ 2,1 ⋅ 10<sup>13</sup> mögliche Start-Anordnungen (<a href="Permutation" title="Permutation">Permutationen</a> der Zahlen 1 bis 16), bei denen das leere 16-te Feld nicht unbedingt unten rechts sitzt.</li>

<li>Durch Verschieben der Steine kann genau die Hälfte aller Startanordnungen in eine aufsteigende Reihenfolge (Sequenz) mit dem leeren Feld unten rechts gebracht werden.<sup id="cite_ref-WoolseyJohnson_4-0" class="reference"><a href="#cite_note-WoolseyJohnson-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Story_1879_5-0" class="reference"><a href="#cite_note-Story_1879-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup></li>

<li>Durch Verschieben der Steine kann die andere Hälfte aller Startanordnungen in eine Sequenz mit dem leeren Feld oben links gebracht werden.</li>

<li>Bei einer Startanordnung, mit der eine Sequenz mit dem leeren Feld oben links erreichbar ist, kann man einer Sequenz mit dem leeren Feld unten rechts lediglich so nahe bringen, dass sich nur zwei der fünfzehn Blöcke an den falschen Positionen befinden.</li></ul>

<p>Für andere Zielanordnungen kann man folgende Sachverhalte feststellen:

</p>

<dl><dd>Lässt sich eine bestimmte Anordnung erreichen, so ist</dd></dl>

<ol><li>die horizontal oder vertikal gespiegelte Anordnung <b>nicht</b> erreichbar.</li>

<li>die um 90° nach rechts oder links gedrehte Anordnung <b>nicht</b> erreichbar.</li>

<li>die um 180° gedrehte Anordnung ebenfalls erreichbar.</li>

<li>die diagonal gespiegelte Anordnung erreichbar.</li>

<li>eine Anordnung, bei der nur zwei benachbarte Steine vertauscht sind, <b>nicht</b> erreichbar.</li></ol>

<div class="gallerytext">Die Hälfte (H1) aller Ausgangsstellungen lässt sich in diese Anordnung bringen.</div>

</li>

<div class="gallerytext">Die andere Hälfte (H2) der Ausgangsstellungen lässt sich in diese Anordnung bringen.</div>

</li>

<div class="gallerytext">Jede zweite Ausgangsstellung (H1) lässt sich nur in diese Anordnung bringen.</div>

</li>

<div class="gallerytext">Die andere Hälfte (H2) lässt sich nur in diese Anordnung bringen.</div>

</li>

</ul>

<div class="mw-heading mw-heading3"><h3 id="15-14-Puzzle">15-14-Puzzle</h3></div>

<p>In der Ausgangsposition des 15-14-Puzzles sind die Steine mit Ausnahme der Steine 14 und 15 schon in aufsteigender Reihenfolge sortiert. Das letzte Feld unten rechts bleibt frei. Bei dieser Ausgangsstellung ist die Aufgabe, die Zahlen durch Verschieben der Steine in die richtige Reihenfolge zu bringen, wobei das letzte Feld wieder frei bleibt, nicht lösbar. Die Aufgabe wird lösbar, wenn man das erste statt des letzten Feldes freilässt (s. o.)

</p>

<div class="mw-heading mw-heading3"><h3 id="14-15-Puzzle">14-15-Puzzle</h3></div>

<p>Eine weitere Möglichkeit besteht darin, aus der geordneten Reihenfolge mit der Lücke unten rechts bestimmte andere Anordnungen zu erreichen, z. B:

</p>

<div class="gallerytext">Ausgangsstellung</div>

</li>

<div class="gallerytext">Erreichbar:<br>Vertikale Anordnung</div>

</li>

<div class="gallerytext">Erreichbar:<br>Eine Spirale</div>

</li>

<div class="gallerytext">Erreichbar:<br>Diese Zick-Zack-Anordnung.</div>

</li>

<div class="gallerytext">Erreichbar:<br>Dieser Springerpfad</div>

</li>

<div class="gallerytext">Nicht erreichbar:<br>Eine Drehung um 90°.</div>

</li>

</ul>

<div class="mw-heading mw-heading3"><h3 id="Modernes_15-Puzzle">Modernes 15-Puzzle</h3></div>

<p>Viele der Spiele, die heute erhältlich sind, sind im Auslieferungszustand bereits richtig sortiert und ihre Steine sind miteinander so verzahnt, dass man sie zwar verschieben, aber nicht entnehmen kann. Das Ziel des Spieles ist es von daher, ein gemischtes Puzzle wieder in den Originalzustand zu versetzen.

</p><p>Im Handel findet man viele Formen dieses Spiels. Es gibt sie beispielsweise als Schlüsselanhänger aus Plastik oder Holz gefertigt.

</p><p>Es gibt auch Spiele, die nicht mehr das Ziel haben, Zahlen zu sortieren, sondern aus einem Bild bestehen, das nur komplett zu sehen ist, wenn alle Quadrate in einer richtigen Reihenfolge sortiert werden.

</p><p>Es gibt Ausführungen mit Buchstaben oder Buchstabengruppen statt Zahlen. Hier soll als Lösung entweder die alphabetische Reihenfolge erreicht werden oder es soll ein bestimmter Text stehen. Letztere haben oft ein Paar (oder gar mehrere) gleicher Kacheln (d. h. mit gleichen Buchstaben). Kommt es dabei zu einer Situation, bei der nur noch die beiden letzten Kacheln vertauscht sind, so muss man ein Paar gleicher Buchstaben tauschen, um die Aufgabe zu lösen. Steht beispielsweise bei dem in der Abbildung „Textversion“ dargestellten Spiel in der unteren Zeile „Prsei“ statt „Preis“, so muss man entweder die beiden „e“, die beiden „n“ oder (!) die beiden „ei“ tauschen.

</p><p>Bei der Darstellung mittels römischer Zahlen erhöht sich der Schwierigkeitsgrad durch die meist schlechtere Übung bei der Zahlenfolge.

</p>

<div class="gallerytext">Version mit Buchstaben</div>

</li>

<div class="gallerytext">Version mit Text</div>

</li>

<div class="gallerytext">Version mit Bild</div>

</li>

<div class="gallerytext">Version mit römischen Zahlen</div>

</li>

<div class="gallerytext">15-Puzzle als Schlüsselanhänger</div>

</li>

</ul>

<div class="mw-heading mw-heading3"><h3 id="Weitere_Aufgabenstellungen">Weitere Aufgabenstellungen</h3></div>

<div class="mw-heading mw-heading4"><h4 id="Magische_Quadrate">Magische Quadrate</h4></div>

<p>Eine weitere Aufgabenstellung für das 15-Puzzle mit Zahlen ist es, die übliche Start-Anordnung (mit dem leeren Feld unten rechts) in ein <a href="Magisches_Quadrat" title="Magisches Quadrat">magisches Quadrat</a> zu überführen, wobei das leere Feld für die Zahl 0 steht.<sup id="cite_ref-LoydGardner_6-0" class="reference"><a href="#cite_note-LoydGardner-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

Die magische Summe (d. h. die Zeilen-, Spalten- und Diagonalensumme) ist dann 30. Berücksichtigt man Drehungen oder Spiegelungen des Quadrats, gibt es 880 <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \cdot }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \cdot }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ba2c023bad1bd39ed49080f729cbf26bc448c9ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.439ex; margin-bottom: -0.61ex; width:0.647ex; height:1.176ex;" alt="{\displaystyle \cdot }" loading="lazy"></span> 8 = 7040 magische Quadrate auf einem <i>4x4</i> -Feld. Von diesen ist genau die Hälfte, also 3520, aus der üblichen Start-Anordnung zu erreichen. Kociemba bestimmte für jedes dieser magischen Quadrate die minimale Anzahl von Zügen, die ausgehend von der Start-Anordnung erforderlich ist. Man benötigt mindestens 35 Züge, um ein magisches Quadrat zu erhalten, und es gibt nur ein einziges magisches Quadrat, das in 35 Zügen erreichbar ist.<sup id="cite_ref-Kociemba_7-0" class="reference"><a href="#cite_note-Kociemba-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Andere_Größen"><span id="Andere_Gr.C3.B6.C3.9Fen"></span>Andere Größen</h2></div>

<p>Es gibt auch Ausführungen in anderen Größen, so z. B. das <i>8-Puzzle</i> in einem Drei-mal-drei-Quadrat und das <i>31-Puzzle</i> in einem Vier-mal-acht-Rechteck.

</p>

<div class="mw-heading mw-heading2"><h2 id="Mathematischer_Hintergrund">Mathematischer Hintergrund</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Permutationen_und_Invarianten">Permutationen und Invarianten</h3></div>

<p>Jede Stellung des Spiels ist entweder <i>lösbar</i> oder <i>unlösbar</i>, das heißt, sie kann in die Endstellung überführt werden oder nicht. Zum <a href="Beweis_(Logik)" title="Beweis (Logik)">Beweis</a> wird die so genannte <a href="Parit%C3%A4t_(Mathematik)" title="Parität (Mathematik)">Parität</a> jeder Stellung betrachtet. Sie bleibt bei einem Zug immer erhalten. Die Parität ergibt sich aus der Anzahl der <i>ungeordneten</i> Zahlenpaare. Dabei ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/71b670ae74954b8aacd4d720d9b2b2081f6d3869.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{1}}" loading="lazy"></span> die Anzahl der Zahlenpaare, die sich in falscher Reihenfolge befinden und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/597ea9dac049261fdda77c5176b050e6588d6bb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{2}}" loading="lazy"></span> die Nummer der Reihe, in der sich das leere Feld befindet. Die Summe <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=N_{1}+N_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=N_{1}+N_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/689a0dd1cdfa2a3c5dfffa633f2e506d865e9748.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.843ex; height:2.509ex;" alt="{\displaystyle N=N_{1}+N_{2}}" loading="lazy"></span> ist entweder <i>gerade</i> oder <i>ungerade</i>. Bei allen erlaubten Zügen bleibt diese Parität erhalten, das heißt eine gerade Spielstellung kann nie in eine ungerade überführt werden und umgekehrt. Da die ursprüngliche Aufgabenstellung <i>ungerade</i> ist, kann sie nie in den <i>geraden</i> Endzustand führen.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p><p>Eine andere Beweisidee verwendet das <a href="Vorzeichen_(Permutation)" title="Vorzeichen (Permutation)">Vorzeichen</a> der als <a href="Permutation" title="Permutation">Permutation</a>, also als Vertauschung, betrachteten Stellung, das mit jedem Zug das <a href="Vorzeichen_(Zahl)" title="Vorzeichen (Zahl)">Vorzeichen</a> wechselt.

</p>

<div class="mw-heading mw-heading3"><h3 id="Beispiel">Beispiel</h3></div>

<p>Um zu überprüfen, ob eine Konstellation von Steinen mittels erlaubter Züge in eine andere überführt werden kann, ist zwischen Rahmengrößen mit geradzahliger (wie der vorliegenden) und solchen mit ungeradzahliger Spaltenanzahl zu unterscheiden. Grundvoraussetzung ist, dass die Steine in der gezeigten Weise nummeriert sind oder bei Puzzles, deren Lösung in der Erstellung eines Bildes liegt, für den Nachweis nummeriert werden. Bei Puzzles, <a href="Mechanische_Geduldspiele" title="Mechanische Geduldspiele">die mehrere Lösungen erlauben</a>, etwa Symbole, die nach bestimmten Regeln angeordnet werden sollen, ist nachzuweisen, dass keine der Lösungsvarianten durch erlaubte Züge erreicht werden kann.

</p><p>Zur Ermittlung des Unordnungsparameters <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/71b670ae74954b8aacd4d720d9b2b2081f6d3869.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{1}}" loading="lazy"></span> zählt man alle Zahlenpaare, bei denen eine kleinere Zahl auf eine größere folgt, unabhängig davon, wie viele Steine dazwischen liegen. Die absolute Größe der jeweiligen Zahlen ist unerheblich, Zahlen können in mehreren Paaren vorkommen. Verglichen werden die Steine so, als wären alle in einer horizontalen Reihe aufgelistet. Bei einer Konstellation von beispielsweise 1, 4, 2, 6, 7, 8, 3, 5 gibt es also folgende Paare: (2, 4), (3, 8), (3, 7), (3, 6), (3, 4), (5, 8), (5, 7), (5, 6). Man <a href="Iteration" title="Iteration">iteriert</a> von links nach rechts und vergleicht eine Zahl mit allen links stehenden Zahlen. Sobald eine links stehende Zahl dann größer ist, wurde ein ungeordnetes Paar gefunden.

</p><p>Wird ein Stein in <i>horizontaler</i> Richtung verschoben, ändern sich weder der Unordnungsparameter <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/71b670ae74954b8aacd4d720d9b2b2081f6d3869.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{1}}" loading="lazy"></span> noch der Reihenparameter <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/597ea9dac049261fdda77c5176b050e6588d6bb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{2}}" loading="lazy"></span>, da man diese Bewegung als Austausch der verschobenen Steine durch das freie Feld auffassen kann, das in der Berechnung des Unordnungsparameters nicht berücksichtigt wird.

</p><p>Wird ein Stein in <i>vertikaler</i> Richtung verschoben, ändert sich der Reihenparameter <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/597ea9dac049261fdda77c5176b050e6588d6bb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{2}}" loading="lazy"></span> um +1 oder − 1. Die vertikale Verschiebung betrifft immer genau drei Zahlenpaare, denn es kann nur Änderungen in der Ordnung zwischen dem verschobenen Stein und den drei eingeschlossenen Feldern geben. Dabei hat sich für jeden eingeschlossenen Stein die Anzahl der ungeordneten Paare um 1 vergrößert oder verkleinert. Da der zu verschiebende Stein seinen Platz getauscht hat, haben nun alle Paare, welche mit dem zu verschiebenden Stein gebildet wurden, ihre Ordnung geändert. Ungeordnete Paare sind nun geordnet und umgekehrt.

</p>

<div class="gallerytext">In dieser Konstellation ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{1}=3}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}=3}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c7446df3c69cbefcf1a873ac861c2ff4711bc566.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.181ex; height:2.509ex;" alt="{\displaystyle N_{1}=3}" loading="lazy"></span>. Die ungeordneten Paare sind <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (11,12),(11,13),}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (11,12),(11,13),}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ca83a67dbe9f7297f784225814f6036f4fdc78dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.667ex; height:2.843ex;" alt="{\displaystyle (11,12),(11,13),}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (11,14)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (11,14)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1493c0d992f3f485b99dca4a5f736d413ef36ad0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.493ex; height:2.843ex;" alt="{\displaystyle (11,14)}" loading="lazy"></span>.</div>

</li>

<div class="gallerytext">Die 7 wechselt vertikal auf das leere Feld, wodurch <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/71b670ae74954b8aacd4d720d9b2b2081f6d3869.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{1}}" loading="lazy"></span> um 3 vergrößert und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/597ea9dac049261fdda77c5176b050e6588d6bb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{2}}" loading="lazy"></span> um 1 verkleinert wird.</div>

</li>

</ul>

<p>In der Anfangskonstellation ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=N_{1}+N_{2}=0+4=4}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=N_{1}+N_{2}=0+4=4}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ebccbf0f35333ec045a2f63fa20a18cca5f5d79a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:26.368ex; height:2.509ex;" alt="{\displaystyle N=N_{1}+N_{2}=0+4=4}" loading="lazy"></span>. Weil sich der Reihenparameter <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/597ea9dac049261fdda77c5176b050e6588d6bb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{2}}" loading="lazy"></span> bei jedem vertikalen Zug um den ungeraden Wert +1 oder −1 ändert und sich der Unordnungsparameter <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/71b670ae74954b8aacd4d720d9b2b2081f6d3869.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{1}}" loading="lazy"></span> dann ebenfalls um den ungeraden Wert +3, +1, −1 oder −3 ändert, ändert sich die Parität <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></span> um +4, +2, 0, −2 oder −4, also jeweils um einen geraden Wert.

</p><p>Die <a href="Parit%C3%A4t_(Mathematik)" title="Parität (Mathematik)">Parität</a> bleibt also nach jedem Zug gerade. Es ist also nicht möglich, von der ursprünglichen Aufgabenstellung, wo die Zahlen 15 und 14 vertauscht sind, zu einer sortierten <a href="Reihenfolge" title="Reihenfolge">Reihenfolge</a> zu gelangen, weil die ursprüngliche Reihenfolge die ungerade Parität <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=5}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=5}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4ea204e60e1d27578912bb557d2859e759f4d67c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.325ex; height:2.176ex;" alt="{\displaystyle N=5}" loading="lazy"></span> hat und nicht mit dem Verschieben von Steinen in eine gerade Parität überführt werden kann.

</p>

<div class="mw-heading mw-heading3"><h3 id="Allgemeinfall">Allgemeinfall</h3></div>

<p>In einem <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\times a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\times a}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6cee5d9936be152fa3084d49b6d293d17e6afbf5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.3ex; height:1.676ex;" alt="{\displaystyle a\times a}" loading="lazy"></span> großen Puzzle mit <i>ungerader</i> Spaltenanzahl <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span> beträgt die Anzahl der Steine <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{2}-1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{2}-1}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/69482e105a906e460712e59a38aa87059ae6f3f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.287ex; height:2.843ex;" alt="{\displaystyle a^{2}-1}" loading="lazy"></span>, ist also eine gerade Zahl. Der Unordnungsparameter <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/71b670ae74954b8aacd4d720d9b2b2081f6d3869.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{1}}" loading="lazy"></span> ändert sich also mit einem horizontalen Zug gar nicht und mit einem vertikalen Zug um eine gerade Zahl. Die <a href="Parit%C3%A4t_(Mathematik)" title="Parität (Mathematik)">Parität</a> des Unordnungsparameters <i><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/71b670ae74954b8aacd4d720d9b2b2081f6d3869.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{1}}" loading="lazy"></span></i> bleibt daher mit jedem Zug erhalten.

</p><p>In einem <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\times a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\times a}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6cee5d9936be152fa3084d49b6d293d17e6afbf5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.3ex; height:1.676ex;" alt="{\displaystyle a\times a}" loading="lazy"></span> großen Puzzle mit <i>gerader</i> Spaltenanzahl <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span> beträgt die Anzahl der eingeschlossenen Steine <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{2}-1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{2}-1}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/69482e105a906e460712e59a38aa87059ae6f3f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.287ex; height:2.843ex;" alt="{\displaystyle a^{2}-1}" loading="lazy"></span>, ist also eine ungerade Zahl. Der Unordnungsparameter <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/71b670ae74954b8aacd4d720d9b2b2081f6d3869.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{1}}" loading="lazy"></span> ändert sich mit einem vertikalen Zug um eine ungerade Zahl. Der Reihenparameter <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/597ea9dac049261fdda77c5176b050e6588d6bb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{2}}" loading="lazy"></span> vergrößert oder verkleinert sich mit jedem vertikalen Zug um 1. Die Änderungen ist also bei jedem vertikalen Zug die Summe aus zwei ungeraden Zahlen und damit gerade. Die Parität von <i><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=N_{1}+N_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=N_{1}+N_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/689a0dd1cdfa2a3c5dfffa633f2e506d865e9748.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.843ex; height:2.509ex;" alt="{\displaystyle N=N_{1}+N_{2}}" loading="lazy"></span></i> bleibt daher mit jedem Zug erhalten.

</p><p>Da die Parität von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/71b670ae74954b8aacd4d720d9b2b2081f6d3869.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{1}}" loading="lazy"></span> bei ungerader oder <i><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=N_{1}+N_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=N_{1}+N_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/689a0dd1cdfa2a3c5dfffa633f2e506d865e9748.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.843ex; height:2.509ex;" alt="{\displaystyle N=N_{1}+N_{2}}" loading="lazy"></span></i> bei gerader Spaltenanzahl stets erhalten bleibt, kann man durch einfaches Abzählen prüfen, ob eine <a href="Zuf%C3%A4llige_Permutation" title="Zufällige Permutation">zufällige Konstellation</a> in eine andere bestimmte Konstellation mittels erlaubter Züge überführt werden kann. Bei der klassischen Aufgabenstellung des 15-Puzzles ist das nicht möglich, da bei gerader Spaltenanzahl <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=4}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a=4}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6d366942ea55e335b92439f564940a422e749648.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.491ex; height:2.176ex;" alt="{\displaystyle a=4}" loading="lazy"></span> die Summe <i><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=N_{1}+N_{2}=1+4=5}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=N_{1}+N_{2}=1+4=5}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/306e0a616ab214ff45f61a65ec885a4b646a42a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:26.368ex; height:2.509ex;" alt="{\displaystyle N=N_{1}+N_{2}=1+4=5}" loading="lazy"></span></i> in die Summe <i><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=N_{1}+N_{2}=0+4=4}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=N_{1}+N_{2}=0+4=4}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ebccbf0f35333ec045a2f63fa20a18cca5f5d79a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:26.368ex; height:2.509ex;" alt="{\displaystyle N=N_{1}+N_{2}=0+4=4}" loading="lazy"></span></i> überführt werden müsste.

</p><p>Des Weiteren zeigen diese Überlegungen, dass höchstens die Hälfte aller denkbaren Konstellationen aus der Anfangskonstellation heraus erreicht werden kann, weil nur Anordnungen von geraden in gerade oder ungeraden in ungerade <a href="Parit%C3%A4t_(Mathematik)" title="Parität (Mathematik)">Paritäten</a> überführt werden können. Wie William Woolsey Johnson und William E. Story 1879 zeigten,<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> ist von der Anfangskonstellation genau diese Hälfte immer erreichbar, was aber durch den hier vorgestellten <a href="Beweis_(Mathematik)" title="Beweis (Mathematik)">Beweis</a> nicht nachgewiesen werden kann, da die Parität lediglich eine <a href="Notwendige_und_hinreichende_Bedingung" title="Notwendige und hinreichende Bedingung">notwendige, nicht aber eine hinreichende Bedingung</a> für die allgemeine Lösbarkeit ist. Einen eleganten modernen Beweis dafür, dass alle Konstellationen von gerader Parität tatsächlich ineinander überführt werden können und auch alle Konstellationen mit ungerader Parität ineinander überführt werden können, gab Aaron F. Archer 1999.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> Auch die im folgenden Kapitel angesprochenen <a href="Algorithmus" title="Algorithmus">Algorithmen</a> für das 15-Puzzle belegen diese Tatsache.

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithmen_und_Komplexität"><span id="Algorithmen_und_Komplexit.C3.A4t"></span>Algorithmen und Komplexität</h2></div>

<p>Schiebepuzzle wie das 8-Puzzle oder das 15-Puzzle dienen seit langem als Testprobleme für <a href="Suchverfahren" title="Suchverfahren">Suchalgorithmen</a> in der <a href="K%C3%BCnstliche_Intelligenz" title="Künstliche Intelligenz">Künstlichen Intelligenz</a>.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> Wie Adrian Brüngger, Ambros Marzetta, Komei Fukuda und Jurg Nievergelt 1999 unter Verwendung eines Intel Paragon <a href="Parallelrechner" title="Parallelrechner">Parallelrechners</a> mit 64 Knoten zeigten, erfordert die Lösung des 15-Puzzles für alle Startkonstellationen maximal 80 Züge.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup>

</p><p>Richard E. Korf und Peter Schultze bestimmten 2005 mittels einer <a href="Breitensuche" title="Breitensuche">Breitensuche</a> und unter Verwendung eines Parallelrechners für jede der <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {16!}{2!}}=10461394944000}">

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {16!}{2!}}=10461394944000}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/957647a3505d1851d3073add6fc7a2b2c91bb005.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:22.31ex; height:3.843ex;" alt="{\displaystyle {\tfrac {16!}{2!}}=10461394944000}" loading="lazy"></span> lösbaren Startkonstellationen die minimale Anzahl der Züge, die zur Lösung notwendig ist. Insbesondere bestimmten sie erstmals alle 17 Startkonstellationen, für die 80 Züge notwendig sind. Eine zufällig gewählte, lösbare Startkonstellation lässt sich in durchschnittlich 52,6 Zügen lösen. Zur Vermeidung von Speicherfehlern – immerhin waren 8 <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \cdot }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \cdot }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ba2c023bad1bd39ed49080f729cbf26bc448c9ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.439ex; margin-bottom: -0.61ex; width:0.647ex; height:1.176ex;" alt="{\displaystyle \cdot }" loading="lazy"></span> 10<sup>14</sup> Bit ≈ 100 Terabyte zu schreiben und zu lesen – verwendeten Korf und Schultze ein <a href="RAID" title="RAID">RAID</a>-System. Dabei wurden 8 <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \cdot }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \cdot }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ba2c023bad1bd39ed49080f729cbf26bc448c9ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.439ex; margin-bottom: -0.61ex; width:0.647ex; height:1.176ex;" alt="{\displaystyle \cdot }" loading="lazy"></span> 10<sup>14</sup> Bit ≈ 100 Terabyte geschrieben und gelesen.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup>

</p><p>Manfred Warmuth und Daniel Ratner bewiesen 1986, dass das verallgemeinerte Problem, die minimale Anzahl Züge zu einer lösbaren Start-Anordnung in einem <i>n x n -</i>Spiel zu finden, <a href="NP-Schwere" title="NP-Schwere">NP-schwer</a> ist.<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>L. E. Horden: <i>Sliding Piece Puzzles</i>. Oxford University Press, 1986, ISBN 0-19-853204-0.</li>

<li>Jerry Slocum, Dic Sonneveld: <i>The 15 Puzzle</i>. Slocum Puzzle Foundation, 2006, ISBN 1-890980-15-3.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Ähnliche_Spiele"><span id=".C3.84hnliche_Spiele"></span>Ähnliche Spiele</h2></div>

<li><a href="Quo_Vadis_(Schiebepuzzle)" title="Quo Vadis (Schiebepuzzle)">Quo Vadis</a> (Klotski)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Jeu_de_taquin" title="Jeu de taquin">Jeu de taquin</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noresize noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"><span class="mw-default-size" typeof="mw:File"><span title="Commons"></span></span></div><b><span class=""><a class="external text" href="https://commons.wikimedia.org/wiki/Category:15_puzzle?uselang=de"><span lang="en">Commons</span>: 15-Puzzle</a></span></b> – Sammlung von Bildern, Videos und Audiodateien</div>

<ul><li><a rel="nofollow" class="external text" href="http://www.mentalmove.com/bine/explanation/fourteen_fifteen.php">The 14-15-Puzzle</a> – Englischsprachige Seite, die den Beweis der Unlösbarkeit des ursprünglichen 15-Puzzles anhand interaktiver Beispiele illustriert.</li>

<li>Herbert Kociemba: <a rel="nofollow" class="external text" href="http://kociemba.org/themen/fifteen/fifteensolver.html">15-Puzzle Optimal Solver</a> mit Download und <a rel="nofollow" class="external text" href="https://github.com/hkociemba/FifteenPuzzle">Programmcode auf Github</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

Jerry Slocum: <i><a rel="nofollow" class="external text" href="http://www.indiana.edu/~liblilly/collections/overview/puzzle_docs/Sam_Loyd_Successful_Hoax.pdf">Sam Loyd's Most Successful Hoax</a>.</i> (PDF; 672 kB). Vortrag auf Seventh Gathering for Gardner, März 2006, The Convention of the Association of Game and Puzzle Collectors. Publiziert in: E. Pegg, A. H. Schoen, T. Rodgers: <i>Homage to a Pied Puzzler.</i> A.K. Peters, Wellesley/Massachusetts 2009, S. 3–21. (hier: S. 4)</span>

</li>

Jerry Slocum, Dic Sonneveld: <i>The 15 Puzzle</i>. Slocum Puzzle Foundation, 2006, ISBN 1-890980-15-3.</span>

</li>

<a rel="nofollow" class="external text" href="http://www.cut-the-knot.org/pythagoras/fifteen.shtml">Sam Loyd's Fifteen</a> Englischsprachige Seite mit Java-Applet und Beweis der Unlösbarkeit des Problems. Abgerufen am 16. November 2007.</span>

</li>

Woolsey Johnson: <i><a rel="nofollow" class="external text" href="http://www.jstor.org/stable/2369492">Notes on the „15“ Puzzle. I</a>.</i> In: <i>Amer. J. Math.</i> 2, 1879, S. 397 bis 399.</span>

</li>

William E. Story: <i><a rel="nofollow" class="external text" href="http://www.jstor.org/stable/2369492">Notes on the „15“ Puzzle. II</a>.</i> In: <i>Amer. J. Math.</i> 2, 1879, S. 399 bis 404.</span>

</li>

Sam Loyd, Martin Gardner: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Mathematical puzzles of Sam Loyd</cite>. Dover Pubs., New York 1959, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>19, 20</span> (englisch, <a rel="nofollow" class="external text" href="https://books.google.de/books?id=QCy6DzgqcI4C&pg=PA20#v=onepage">eingeschränkte Vorschau</a> in der Google-Buchsuche).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:15-Puzzle&rft.au=Sam+Loyd%2C+Martin+Gardner&rft.btitle=Mathematical+puzzles+of+Sam+Loyd&rft.date=1959&rft.genre=book&rft.pages=19%2C+20&rft.place=New+York&rft.pub=Dover+Pubs." style="display:none"> </span></span>

</li>

Herbert Kociemba: <a rel="nofollow" class="external text" href="http://kociemba.org/themen/fifteen/fifteensolver.html">15-Puzzle Optimal Solver</a> 2013.</span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><a href="#cite_ref-8">↑</a></span> <span class="reference-text">Wilhelm Ahrens: <cite style="font-style:italic">Mathematische Spiele</cite>. Anaconda, 2008, ISBN 978-3-86647-203-7, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>21–30</span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:15-Puzzle&rft.au=Wilhelm+Ahrens&rft.btitle=Mathematische+Spiele&rft.date=2008&rft.genre=book&rft.isbn=9783866472037&rft.pages=21-30&rft.pub=Anaconda" style="display:none"> </span></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><a href="#cite_ref-9">↑</a></span> <span class="reference-text">Wm. Woolsey Johnson, William E. Story: <cite style="font-style:italic">Notes on the "15" Puzzle</cite>. In: <cite style="font-style:italic">American Journal of Mathematics</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>2</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>4</span>, Dezember 1879, <a href="Internationale_Standardnummer_f%C3%BCr_fortlaufende_Sammelwerke" title="Internationale Standardnummer für fortlaufende Sammelwerke">ISSN</a> <span style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://zdb-katalog.de/list.xhtml?t=iss%3D%220002-9327%22&key=cql">0002-9327</a></span>, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>397–404</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.2307/2369492">10.2307/2369492</a></span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:15-Puzzle&rft.atitle=Notes+on+the+%2215%22+Puzzle&rft.au=Wm.+Woolsey+Johnson%2C+William+E.+Story&rft.date=1879-12&rft.doi=10.2307%2F2369492&rft.genre=journal&rft.issn=0002-9327&rft.issue=4&rft.jtitle=American+Journal+of+Mathematics&rft.pages=397-404&rft.volume=2" style="display:none"> </span></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><a href="#cite_ref-10">↑</a></span> <span class="reference-text">Aaron F. Archer: <cite style="font-style:italic">A Modern Treatment of the 15 Puzzle</cite>. In: <cite style="font-style:italic">The American Mathematical Monthly</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>106</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>9</span>, November 1999, <a href="Internationale_Standardnummer_f%C3%BCr_fortlaufende_Sammelwerke" title="Internationale Standardnummer für fortlaufende Sammelwerke">ISSN</a> <span style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://zdb-katalog.de/list.xhtml?t=iss%3D%220002-9890%22&key=cql">0002-9890</a></span>, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>793–799</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1080/00029890.1999.12005124">10.1080/00029890.1999.12005124</a></span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:15-Puzzle&rft.atitle=A+Modern+Treatment+of+the+15+Puzzle&rft.au=Aaron+F.+Archer&rft.date=1999-11&rft.doi=10.1080%2F00029890.1999.12005124&rft.genre=journal&rft.issn=0002-9890&rft.issue=9&rft.jtitle=The+American+Mathematical+Monthly&rft.pages=793-799&rft.volume=106" style="display:none"> </span></span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><a href="#cite_ref-11">↑</a></span> <span class="reference-text"><span class="cite">Richard E. Korf, Larry A. Taylor: <a rel="nofollow" class="external text" href="https://cdn.aaai.org/AAAI/1996/AAAI96-178.pdf"><i>Finding Optimal Solutions to the Twenty-Four Puzzle.</i></a> (PDF) In: <i>Proceedings of the 11th National Conference on Artificial Intelligence.</i> <a href="University_of_California%2C_Los_Angeles" title="University of California, Los Angeles">University of California, Los Angeles</a>, Juli 1993, <span style="white-space:nowrap;">S. 756–761</span>,<span class="Abrufdatum"> abgerufen am 15. April 2025</span>.</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3A15-Puzzle&rft.title=Finding+Optimal+Solutions+to+the+Twenty-Four+Puzzle&rft.description=Finding+Optimal+Solutions+to+the+Twenty-Four+Puzzle&rft.identifier=https%3A%2F%2Fcdn.aaai.org%2FAAAI%2F1996%2FAAAI96-178.pdf&rft.creator=Richard+E.+Korf%2C+Larry+A.+Taylor&rft.publisher=%5B%5BUniversity+of+California%2C+Los+Angeles%5D%5D&rft.date=1993-07"> </span></span>

</li>

<li id="cite_note-12"><span class="mw-cite-backlink"><a href="#cite_ref-12">↑</a></span> <span class="reference-text"><span class="cite">Adrian Brüngger, Ambros Marzetta, Komei Fukuda, Jurg Nievergelt: <a rel="nofollow" class="external text" href="https://www.iro.umontreal.ca/~gendron/Pisa/References/BB/Brungger99.pdf"><i>The parallel search bench ZRAM and its applications.</i></a> (PDF) In: <i>Annals of Operations Research 90.</i> 1999, <span style="white-space:nowrap;">S. 45–63</span>,<span class="Abrufdatum"> abgerufen am 15. April 2025</span>.</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3A15-Puzzle&rft.title=The+parallel+search+bench+ZRAM+and+its+applications&rft.description=The+parallel+search+bench+ZRAM+and+its+applications&rft.identifier=https%3A%2F%2Fwww.iro.umontreal.ca%2F%7Egendron%2FPisa%2FReferences%2FBB%2FBrungger99.pdf&rft.creator=Adrian+Br%C3%BCngger%2C+Ambros+Marzetta%2C+Komei+Fukuda%2C+Jurg+Nievergelt&rft.date=1999"> </span></span>

</li>

<li id="cite_note-13"><span class="mw-cite-backlink"><a href="#cite_ref-13">↑</a></span> <span class="reference-text"><span class="cite">Richard E. Korf, Peter Schultze: <a rel="nofollow" class="external text" href="https://cdn.aaai.org/AAAI/2005/AAAI05-219.pdf"><i>Large-Scale Parallel Breadth-First Search.</i></a> (PDF) In: <i>Proceedings of the 20th National Conference on Artificial Intelligence.</i> <a href="University_of_California%2C_Los_Angeles" title="University of California, Los Angeles">University of California, Los Angeles</a>, 9. Juli 2005, <span style="white-space:nowrap;">S. 1380–1385</span>,<span class="Abrufdatum"> abgerufen am 15. April 2025</span>.</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3A15-Puzzle&rft.title=Large-Scale+Parallel+Breadth-First+Search&rft.description=Large-Scale+Parallel+Breadth-First+Search&rft.identifier=https%3A%2F%2Fcdn.aaai.org%2FAAAI%2F2005%2FAAAI05-219.pdf&rft.creator=Richard+E.+Korf%2C+Peter+Schultze&rft.publisher=%5B%5BUniversity+of+California%2C+Los+Angeles%5D%5D&rft.date=2005-07-09"> </span></span>

</li>

<li id="cite_note-14"><span class="mw-cite-backlink"><a href="#cite_ref-14">↑</a></span> <span class="reference-text"><span class="cite">Manfred Warmuth, Daniel Ratner: <a rel="nofollow" class="external text" href="https://aaai.org/papers/00168-aaai86-027-finding-a-shortest-solution-for-the-n-x-n-extension-of-the-15-puzzle-is-intractable/"><i>Finding a Shortest Solution for the N x N Extension of the 15-PUZZLE Is Intractable.</i></a> In: <i>Proceedings of the AAAI Conference on Artificial Intelligence, 5.</i> <a href="University_of_California%2C_Santa_Cruz" title="University of California, Santa Cruz">University of California, Santa Cruz</a>, 1986,<span class="Abrufdatum"> abgerufen am 15. April 2025</span>.</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3A15-Puzzle&rft.title=Finding+a+Shortest+Solution+for+the+N+x+N+Extension+of+the+15-PUZZLE+Is+Intractable&rft.description=Finding+a+Shortest+Solution+for+the+N+x+N+Extension+of+the+15-PUZZLE+Is+Intractable&rft.identifier=https%3A%2F%2Faaai.org%2Fpapers%2F00168-aaai86-027-finding-a-shortest-solution-for-the-n-x-n-extension-of-the-15-puzzle-is-intractable%2F&rft.creator=Manfred+Warmuth%2C+Daniel+Ratner&rft.publisher=%5B%5BUniversity+of+California%2C+Santa+Cruz%5D%5D&rft.date=1986"> </span></span>

</li>

</ol>

<p><br>

</p>

</div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-06-20" href="https://de.wikipedia.org/wiki/?title=15-Puzzle&oldid=257197130">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>